#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        auto cmp = [&nums1, &nums2](const pair<int, int>& a, const pair<int, int>& b) -> bool {
            return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
        };
        //优先队列中的元素为 [第一个数，第二个数，第二个数的下标]
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
        for(int i = 0; i < nums1.size(); i++){
            q.emplace(i, 0);
        } 
        vector<vector<int>>ans;
        while(k-- && !q.empty()){
            auto [x, y] = q.top();
            q.pop();
            ans.emplace_back(initializer_list<int>{nums1[x], nums2[y]});
            if(++y >= nums2.size())continue;
            q.emplace(x, y);
        }
        return ans;
    }
};

/**
 * @brief 2022.2.23
 * 多路归并
 * 
 */